package 力扣日常刷题.木22一月.第12天0120;

/**
 * @author 帅小伙
 * @date 2022/1/20
 * @description
 */
public class Demo29动态规划中等叶值的最小代价生成树 {


    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int[][] maxValue = new int[n][n];

        for (int i = 0; i < n; i++) {
            maxValue[i][i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                maxValue[i][j] = Math.max(maxValue[i][j - 1], arr[j]);
            }
        }
        //划分成 i-j   j-i+len
        for (int len = 1; len < n; len++) {
            for (int i = 0; i + len < n; i++) {
                dp[i][i + len] = Integer.MAX_VALUE;
                for (int j = i; j < i + len; j++) {
                    dp[i][i + len] = Math.min(dp[i][i + len], dp[i][j] + dp[j + 1][i + len] + maxValue[i][j] * maxValue[j + 1][i + len]);
                }
            }
        }
        return dp[0][n - 1];
    }

}
